#include <stdio.h>
#include "SeqTree.h"

/**
 * 初始化二叉树
 * @param tree
 */
void InitSeqTree(SeqBinTree tree) {
    /* 将字符数组中的每个元素赋值为0 */
    for (int i = 0; i < MAX_SIZE; i++) {
        tree[i] = '\0';
    }
}


/**
 * 创建二叉树
 * @param tree
 * @param index 数组中的下标
 */
void CreateSeqTree(SeqBinTree tree, int index) {
    char ch;
    /* 获取输入的字符 */
    ch = getchar();
    /*
     * fflush是一个在C语言标准输入输出库中的函数，功能是冲洗流中的信息，
     * 该函数通常用于处理磁盘文件。fflush()会强迫将缓冲区内的数据写回参
     * 数stream 指定的文件中。
     *
     * stdin是标准输入，一般指键盘输入到缓冲区里的东西。
     * */
    fflush(stdin);
    /* "."代表该节点为空  */
    if (ch == '.') {
        /* 将tree的的该位置元素赋值为 '\0' */
        tree[index] = '\0';
        return;
    } else {
        /* 如果不为空,i 获取输入的元素 */
        tree[index] = ch;
        /* 某个节点输入完毕后,还需要让用户做孩子和右孩子 */
        printf("place input left child: ");
        /* 左孩子计算公式: */
        CreateSeqTree(tree, 2 * index + 1);
        printf("place input right child: ");
        CreateSeqTree(tree, 2 * (index + 1));
    }

}

/**
 * 输出树
 * @param tree
 */
void PrintTree(SeqBinTree tree) {
    for (int index = 0; index < 5; index++) {
        printf("%-3c", tree[index]);
    }
}


/**
 * 先序遍历二叉树
 * @param tree
 */
void PreOrder(SeqBinTree tree) {
    if (tree) {}
}

/**
 * 中序遍历二叉树
 * @param tree
 */
void InOrder(SeqBinTree tree) {}


/**
 * 获取树的根节点
 * @param tree
 * @return 返回第一个位置的元素值
 */
char GetSeqTreeRoot(SeqBinTree tree) {
    return tree[0];
}

/**
 * 获取树的节点总数
 * @param tree
 * @return
 */
int GetSeqTreeLength(SeqBinTree tree) {
    /**
     * 如果要从头部开始遍历，中间会存在 '\0'导致计算长度中断, 算出的不是最终结果,
     * 正确的方式应该是: 从尾部找非'\0'的叶节点,排除尾部所有的 '\0',剩下的就是二叉树
     * 顺序存储结构
     */
    int len;
    for (len = MAX_SIZE; len >= 1; len--) {
        if (tree[len - 1] != '\0') {
            break;
        }
    }
    return len;
}


/**
 * 获取树的深度
 * @param tree
 * @return
 */
int GetSeqTreeDepth(SeqBinTree tree) {
    /* 性质2: 深度为 k 的二叉树最多有 2^k-1个节点 */
    int depth = 0;
    int len = GetSeqTreeLength(tree);
    while ((int) pow(2, depth) - 1 < len) {
        depth++;
    }
    return depth;
}